package leetcodev1.树;

import leetcodev1.链表.Solution;

import java.util.*;

public class LeetCode94 {
    //中序遍历 左中右
    //1.递归
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        helper(ret, root);
        return ret;
    }

    private void helper(List<Integer> ret, TreeNode node) {
        if (node == null) {
            return;
        }

        helper(ret, node.left);
        ret.add(node.val);
        helper(ret, node.right);
    }

    public static void main(String[] args) {
        LeetCode94 leetCode94 = new LeetCode94();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.right = node2;
        node2.left = node3;
        leetCode94.inorderTraversal(node1);
    }

    //2.非递归
    //利用栈模拟递归(找准起点 最左边的元素是起点)
    //链表最好也是用前继指针去验证
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.peek();
            if (node.left != null) {
                stack.push(node.left);
            } else {
                TreeNode pop = stack.pop();//出栈
                ret.add(pop.val);
                if (pop.right != null) {
                    //应该将右节点处理成最左元素
                    stack.push(pop.right);//每次都会将右节点重新加入 bug
                }
            }
        }

        return ret;
    }
}

class Answer94 {
    //将树抽象成一个斜着的队列
    //利用栈模拟出递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            //将所有最左元素入栈
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}
